//
//  15. 三数之和.swift
//  Top600
//
//  Created by rjb on 2021/8/6.
//

import Foundation
class Solution15 {
    // 三数之和
    // a+b+c = 0
    // 不能重复的三元组
    // a + b = -c
    // 暴力解法是三层for循环，
    // 通过双指针能减轻一层循环；
    // 不重复，先排序，相连相同去掉
    //
    func threeSum(_ nums: [Int]) -> [[Int]] {
        guard nums.count >= 3 else {
            return []
        }
        // 对数组排序
        let nums = nums.sorted()
        
        var result: [[Int]] = []
        for cIndex in 0..<nums.count {
            // 去除重复的
            if cIndex > 0 && nums[cIndex] == nums[cIndex - 1] {
                continue
            }
            var aIndex = cIndex + 1
            var bIndex = nums.count - 1
            while aIndex < bIndex {
                let sum = nums[aIndex] + nums[bIndex] + nums[cIndex]
                if sum < 0 {
                    // 说明小了，a向右移动
                    aIndex += 1
                } else if sum == 0 {
                    // 说明相等
                    result.append([nums[aIndex],nums[bIndex],nums[cIndex]])
                    // 继续寻找，但不要让aIndex重复
                    while aIndex < bIndex, nums[aIndex] == nums[aIndex + 1] {
                        aIndex += 1
                    }
                    while aIndex < bIndex, nums[bIndex] == nums[bIndex - 1] {
                        bIndex -= 1
                    }
                    aIndex += 1
                    bIndex -= 1
                } else {
                    // 说明大了，b向左移动
                    bIndex -= 1
                }
            }
        }
        return result
    }
    static func test() {
        let solution = Solution15()
        let nums = [-1,0,1,2,-1,-4]
        let result = solution.threeSum(nums)
        print(result)
    }
}
